/**
 * Written By: MinHo Kim (minho.kim.korea@gmail.com)
 * Copyright (C) 2011, MinHo Kim, Software Expert Program, KAIST University, Seoul, Korea.
 * This program is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU General Public License as published 
 * by the Free Software Foundation; version 2 of the License.
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; 
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
 * See the GNU General Public License for more details.
 */
package kaist.sep502.tsp.algorithm.heuristic;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

import kaist.sep502.tsp.model.CityPath;
import kaist.sep502.tsp.model.Problem;
import kaist.sep502.tsp.util.TspUtil;

/**
 * @author minho kim
 *
 */
public class GreedySearchHeuristic implements HeuristicAlgorithm {
	private Heuristic heuristic = new Heuristic();
	private CityPath cityPath;
	private Problem problem;
	private long expandedCount =0;
	
	/* (non-Javadoc)
	 * @see kaist.sep502.tsp.algorithm.heuristic.HeuristicAlgorithm#getHx(kaist.sep502.tsp.model.CityPath)
	 */
	@Override
	public Heuristic getHx(Problem problem, CityPath cityPath) throws Exception {
		this.heuristic.hx = 0.0;
		this.heuristic.cityNo = problem.goalCityNo;
		this.cityPath = cityPath;
		this.problem = problem;
		
		setHeuristic();
		
		return heuristic;
	}
	
	/* (non-Javadoc)
	 * @see kaist.sep502.tsp.algorithm.heuristic.HeuristicAlgorithm#getHx(kaist.sep502.tsp.model.CityPath, int)
	 */
	@Override
	public Heuristic getHx(Problem problem, CityPath cityPath, int nextCityNo) throws Exception {
		this.heuristic.hx = 0.0;
		this.heuristic.cityNo = nextCityNo;
		this.cityPath = cityPath;
		this.problem = problem;
		
		setHeuristic(nextCityNo);
		
		return heuristic;
	}

	protected void setHeuristic() throws Exception{
		PriorityQueue<CityPath> minimumSpanningTree = new PriorityQueue<CityPath>();
		
		// i : cityNo가 아님.
		int tempCityNo;
		for(int i=0; i<problem.citySize; i++){
			tempCityNo = problem.cityList.get(i).getCityNo();
			if(cityPath.tourHistory.contains(tempCityNo)){
				continue;
			}

			CityPath msCityPath = getMinimalSpanningCityPath(tempCityNo, problem.goalCityNo);
			minimumSpanningTree.add(msCityPath);
		}
		
		CityPath bestOne = minimumSpanningTree.poll();
		
		if(bestOne == null){ // tour is over
//			heuristic.cityNo = 0;
			heuristic.hx = 0.0;
		} else {
			heuristic.cityNo = bestOne.getLastCity();
			heuristic.hx = bestOne.hx;
		}
	}
	
	protected void setHeuristic(int nextCityNo) throws Exception{
		CityPath bestOne = getMinimalSpanningCityPath(nextCityNo, problem.goalCityNo);
		
		if(bestOne == null){ // tour is over
			heuristic.hx = 0.0;
		} else {
			heuristic.hx = bestOne.hx;
		}
	}
	
	/**
	 * return one citypath that has all route from baseCityPath to 'to'(usually goalCity)
	 * this is for g(from) and h(from)
	 *  
	 * @param baseCityPath : current City Path
	 * @param from : next route for traveling
	 * @param to : goal city
	 * @return CityPath : Path = baseCity ~ from; g(x) = baseCity ~ from; h(x) = from ~ to  
	 * @throws Exception 
	 */
	protected CityPath getMinimalSpanningCityPath(int from, int to) throws Exception {
		CityPath fromCityPath = cityPath.clone();
		double hx = 0.0;
		fromCityPath.moveTo(problem, from, hx);
		int currentCityNo = from;
		List<Integer> visitedList = new ArrayList<Integer>();
		TspUtil.mergeList(visitedList, fromCityPath.tourHistory);
		TspUtil.mergeList(visitedList, cityPath.tourHistory);
		
		do {
			expandedCount++;
			from = currentCityNo; // temporary
			currentCityNo = problem.getClosestCityNo(currentCityNo, visitedList);
			
			if(currentCityNo == problem.goalCityNo){ // if it can't find the closest city, it means it travled all cities.
				currentCityNo = to;
			}
			
			
			fromCityPath.addHx(problem.calculateDistance(problem.getCity(from), problem.getCity(currentCityNo)));
			visitedList.add(currentCityNo);
		} while(currentCityNo != to);
		
		return fromCityPath;
	}

	public long getExpandedCount(){
		return expandedCount;
	}
	
}